package double_pointer;

import java.util.Arrays;

public class nextPermutation {
    public static void main(String[] args) {
    int[ ] s = new int[]{5,1,4,2,3};
            nextPermutation(s);
        for (int x :
                s) {
            System.out.print(x+" ");
        }
    }
    public  static void nextPermutation(int[] nums) {

        int n = nums.length - 1;
        int min = n;
        int index = n;

        // 开始寻找右边比左边大的2个数 ，右边的数下标为index
        while (  index > 0&&nums[index - 1] >= nums[index]) {
            index--;
        }
        // 从右往左，找到第一个大于index-1的数
        while( index > 0&&nums[index-1] >= nums[min]) {
            min--;
        }
        // 如果idex = 0，此时已经是最大的，需要重新排序
        if (index == 0) {
            Arrays.sort(nums);

        } else {

            // 交换最小的数和 左边的数
            int tem = nums[min];
            nums[min] = nums[index - 1];
            nums[index - 1] = tem;

            // 开始对index-1 之后数组进行升序排序
            Arrays.sort(nums, index, n+1);
        }

    }
}
